//给你一个字符串 s ，颠倒字符串中 单词 的顺序。 
//
// 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 
//
// 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 
//
// 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "the sky is blue"
//输出："blue is sky the"
// 
//
// 示例 2： 
//
// 
//输入：s = "  hello world  "
//输出："world hello"
//解释：颠倒后的字符串中不能存在前导空格和尾随空格。
// 
//
// 示例 3： 
//
// 
//输入：s = "a good   example"
//输出："example good a"
//解释：如果两个单词间有多余的空格，颠倒后的字符串需要将单词间的空格减少到仅有一个。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 10⁴ 
// s 包含英文大小写字母、数字和空格 ' ' 
// s 中 至少存在一个 单词 
// 
//
// 
// 
//
// 
//
// 进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。 
// Related Topics 双指针 字符串 👍 491 👎 0

package leetcode.editor.cn;

import com.sun.org.apache.bcel.internal.generic.NEW;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

class ReverseWordsInAString {
    public static void main(String[] args) {
        Solution solution = new ReverseWordsInAString().new Solution();
        solution.reverseWords("  hello world  ");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /* public String reverseWords(String s) {
            // 去除首尾空格
            StringBuilder sb = removeSpace(s);
            // 反转所有字符
            reverseString(sb, 0, sb.length() - 1);
            // 反转其中单词
            reverseEachWord(sb);
            return String.valueOf(sb);
        }

        *//**
         * 去掉空格
         *
         * @param s
         * @return
         *//*
        private StringBuilder removeSpace(String s) {
            StringBuilder sb = new StringBuilder();
            int start = 0, end = s.length() - 1;
            // 去掉首尾空格
            while (s.charAt(start) == ' ') start++;
            while (s.charAt(end) == ' ') end--;

            while (start <= end) {
                // 不存在空格追加进去
                char c = s.charAt(start);
                // 后面 sb.charAt(sb.length() - 1) != ' ' 处理中间有2个空格的情况
                if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                    sb.append(c);
                }
                start++;
            }
            return sb;
        }

        *//**
         * 反转字符串指定区间[start, end]的字符
         *
         * @param sb
         * @param start
         * @param end
         *//*
        public void reverseString(StringBuilder sb, int start, int end) {
            for (; start < end; start++, end--) {
                char temp = sb.charAt(start);
                sb.setCharAt(start, sb.charAt(end));
                sb.setCharAt(end, temp);
            }
        }

        */

        /**
         * 反转每个单词
         *
         * @param sb
         *//*
        private void reverseEachWord(StringBuilder sb) {
            int start = 0, end = 1;
            int n = sb.length();
            while (start < n) {
                // 搜索一个单词
                while (end < n && sb.charAt(end) != ' ') {
                    end++;
                }

                // 反转这个单词
                reverseString(sb, start, end - 1);

                // 重新开始下一个单词
                start = end + 1;
                end = start + 1;
            }
        }*/

        // 使用栈
        public String reverseWords(String s) {
            int n = s.length();
            if (s == null || n == 0) return null;

            int l = 0, r = n - 1;
            // 去掉首尾空格
            while (l < r && s.charAt(l) == ' ') l++;
            while (l < r && s.charAt(r) == ' ') r--;

            Deque<String> deque = new LinkedList<>();
            StringBuilder word = new StringBuilder();

            while (l <= r) {
                char c = s.charAt(l);
                // 遇到空格就将单词队列前边
                if (word.length() != 0 && c == ' ') {
                    deque.offerFirst(word.toString());
                    word.delete(0, word.length());
                    // word.setLength(0);
                } else if (c != ' ') {
                    // 注意要判断，防止中间有2个空格的情况
                    // 没遇到就组装单词
                    word.append(c);
                }
                l++;
            }
            // 最后一个单词，没有空格来区分，所以需要多加入一次
            deque.offerFirst(word.toString());

            // 组装空格
            return String.join(" ", deque);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
